#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//---------------------instruction------------------------------------------
/*Author: Jack Guobin Hui*/
/*This program is implemented by C  */
/*Use Stack and backtracking method to search the maze's path.*/
/*Use Matrix transposition, to match the example. column as row, and row as column.*/
/*Reversed the linked stack to print the passed points by order.*/
/*Make the maze size as fix, (7, 11), however, could make it dynamic if need.*/


//--------------------Fixed Bugs------------------------------------------------

//1. Use the same node to store the stack data. 
//ElemType temp_elem;------------------>   temp_elem = (ElemType *)malloc(sizeof(ElemType));

//2. array over the edge.
//i = 0; i != maze->row; i += maze->row-1---------------->i = 0; i < maze->row; i += maze->row-1

//3. wrong logic to find the exit point. image an exit point on (1,3), it's corridor == 1, j != 0, but i == 1!
//corridor == maze->array_maze[i][j] && i != 1 && j != 0-------------->corridor == maze->array_maze[i][j] && i != 1 && j != 0

//4. Memery leak at function delete_maze:  freed maze, but do not free array_maze.

//5. In function get_next_position: May out of array range when search in west or north direction.

//6. In function init_maze: the two-dimensional array parameter make all kinds of crash.

//7. In function init_maze: use the wrong type to memset: memset(temp, 0, sizeof(MazeType *));

//8. In function init_maze_3: use element error: temp->array_maze[i][j] = *((int *)array + j*row + i);-------------->temp->array_maze[i][j] = *((int *)array + j*column + i);


//----------------------constants---------------------------------------
#define TRUE 1
#define FALSE 0
#define MAX_ROW 100                                  /*Max maze row*/
#define MAX_COLUMN 100                             /*Max maze column*/
#define ARRAY_ROW 7                                  /*The array's row size which used to init(copy to) the maze*/
#define ARRAY_COLUMN 11                           /*The array's column size which used to init(copy to) the maze*/



//----------------------variables----------------------------------------
typedef void * DataType;

//This type stands for the row/column number in the maze.
typedef struct
{
	int row;
	int col;
}PointType;

//The node which will be store in the stack.
typedef struct
{
	PointType point;
	int direction;
}ElemType;

//The maze structure
typedef struct
{
	int row;
	int column;
	PointType entry_point;
	PointType exit_point;
	int array_maze[MAX_ROW][MAX_COLUMN];
}MazeType;

//Linked Stack structure
typedef struct node{
	DataType data;
	struct node *link;
} LinkedNode, *LinkStack;

//The point status
typedef enum {wall, corridor, passed, dead_end}PointStatus;

//Search direction, clockwisely search from the east direction.
typedef enum {east = 1, south, west, north}DirectionType;



//--------------------------functions----------------------------------------

//stack functions
int push(LinkedNode **stack, void *data);
int pop(LinkedNode **stack, void **data);
int create(LinkedNode **stack);
int destory(LinkedNode *stack);
int is_stack_empty(LinkedNode *stack);
int reverse_stack(LinkedNode **stack);
int print_stack(LinkedNode *stack);

//maze operation functions
int pass(MazeType *maze, PointType *current_point);
int get_exit_point(MazeType *maze, PointType *exit_point);
int reach_exit(PointType *current_point, PointType *exit_point);
void mark_passed_point(MazeType *maze, PointType *current_point);
void mark_unavailable_point(MazeType *maze, PointType *current_point);
int get_next_position(PointType *current_point, int direction);
int init_maze_3(MazeType **maze,  int **array, int row, int column);
int init_maze_2(MazeType **maze,  int *array, int row, int column);
int init_maze_1(MazeType **maze, int (*array)[ARRAY_COLUMN], int row, int column);
//int init_maze_1(MazeType **maze, int *array, int row, int column);
//int init_maze_1(MazeType **maze, int **array, int row, int column);
int init_maze(MazeType **maze, int **array, int row, int column);
int delete_maze(MazeType *maze);
void print_maze(MazeType *maze);
int maze_path(MazeType *maze, PointType *entry_point, PointType *exit_point);

//functions implement
int push(LinkedNode **stack, void *data)
{
	LinkedNode *temp = NULL;
	temp = (LinkedNode *)malloc(sizeof(LinkedNode));
	if(NULL == temp)
	{
		return -1;
	}

	temp->data = data;
	temp->link = *stack;
	*stack = temp;
	return 0;
}

int pop(LinkedNode **stack, void **data)
{
	LinkedNode *temp = NULL;
	if(!(temp = *stack))
	{
		return -1;
	}

	*data = temp->data;
	*stack = temp->link;
	free(temp);
	return 0;
	
}

int create(LinkedNode **stack)
{
	*stack = NULL;
	return 0;
}

int destory(LinkedNode *stack)
{
	LinkedNode *temp = stack;
	LinkedNode *temp1 = NULL;
	while(NULL != temp)
	{
		temp1 = temp;
		temp = temp->link;
		free(temp1);
		temp1 = NULL;
	}
	return 0;
}

//If empty, return true, else return false.
int is_stack_empty(LinkedNode *stack)
{
	if(NULL == stack)
	{
		return TRUE;
	}
	return FALSE;
}

int reverse_stack(LinkedNode **stack)
{
	LinkedNode *temp = NULL;
	LinkedNode *pre = NULL;
	LinkedNode *cur = NULL;

	cur = *stack;
	
	if(NULL == cur || NULL == cur->link)
	{
		return TRUE;
	}

	while(cur->link)
	{
		temp = pre;
		pre = cur;
		cur = cur->link;
		pre->link = temp;
	}

	cur->link = pre;
	*stack = cur;

	return TRUE;
	
}

int print_stack(LinkedNode *stack)
{
	int row = 0;
	int col = 0;

	do
	{
		row = ((ElemType *)(stack->data))->point.row;
		col = ((ElemType *)(stack->data))->point.col;
		printf("(%d,%d)", row, col);
		stack = stack->link;
	}
	while(NULL != stack);
	
	return TRUE;
}

//If current point is a corridor(not passed or dead_end corridor), return true; else return false.
int pass(MazeType *maze, PointType *current_point)
{
	if(corridor == maze->array_maze[current_point->row][current_point->col])
	{
		return TRUE;
	}
	return FALSE;
}

//Search in the maze to get the exit point.
int get_exit_point(MazeType *maze, PointType *exit_point)
{
	int i = 0;
	int j = 0;

	//Search the top&bottom edge.
	for(i = 0; i < maze->row; i += maze->row-1)
	{
		for(j = 0; j < maze->column; ++j)
		{
			//make sure it is not the entry point
			if(corridor == maze->array_maze[i][j] && (i != 1 || j != 0))  
			{
				exit_point->row = i;
				exit_point->col = j;
				return TRUE;
			}
		}
	}

	//Search the top&bottom edge.
	for(i = 0; i < maze->row; ++i)
	{
		for(j = 0; j < maze->column; j += maze->column -1)
		{
			//make sure it is not the entry point
			if(corridor == maze->array_maze[i][j] && (i != 1 || j != 0))
			{
				exit_point->row = i;
				exit_point->col = j;
				return TRUE;
			}
		}
	}

	return FALSE;
}

int reach_exit(PointType *current_point, PointType *exit_point)
{
	if(current_point->row == exit_point->row && current_point->col == exit_point->col)
	{
		return TRUE;
	}
	return FALSE;
}

//If a point is passed, it will not available
void mark_passed_point(MazeType *maze, PointType *current_point)
{
	maze->array_maze[current_point->row][current_point->col] = passed;
	return;
}

//If a point is a dead end point, it will not available
void mark_unavailable_point(MazeType *maze, PointType *current_point)
{
	maze->array_maze[current_point->row][current_point->col] = dead_end;
	return;
}

//Get the next position from the given point, start from the east, by clockwise.
int get_next_position(PointType *current_point, int direction)
{
	switch (direction)
	{
		case east:
			current_point->col++;
			break;
		case south:
			current_point->row++;
			break;
		case west:
			current_point->col--;

			//crossed  the west edge of array
			if(current_point->col < 0)
			{
				current_point->col++;
				return FALSE;
			}
			break;
		case north:
			current_point->row--;

			//crossed  the north edge of array
			if(current_point->row < 0)
			{
				current_point->row++;
				return FALSE;
			}
			break;
		default:
			break;
	}
	
	return TRUE;
}

int init_maze_3(MazeType **maze,  int **array, int row, int column)
{
	int i, j;
	MazeType *temp = NULL;
	temp = (MazeType *)malloc(sizeof(MazeType));
	if(NULL == temp)
	{
		printf("error!\n");
		return -1;
	}

	memset(temp->array_maze, 0, sizeof(temp->array_maze));
	
	//Matrix transposition, to match the example.
	for(i = 0; i != column; ++i)
	{
		for(j = 0; j != row; ++j)
		{
			//temp->array_maze[i][j] = array[j*column + i];
			temp->array_maze[i][j] = *((int *)array + j*column + i);
			//temp->array_maze[i][j] = array[j][i];
			//temp->array_maze[i][j] = *(*(array+j)+i);
			//printf("%d\n", array[j][i]);
		}
		
	}

	temp->row = column;
	temp->column = row;

	//init the entry point
	temp->entry_point.row = 1;
	temp->entry_point.col = 0;

	//init the exit point
	if(!get_exit_point(temp, &temp->exit_point))
	{
		free(temp);
		temp = NULL;
		return FALSE;
	}
	*maze = temp;
	return TRUE;
}

int init_maze_2(MazeType **maze,  int *array, int row, int column)
{
	int i, j;
	MazeType *temp = NULL;
	temp = (MazeType *)malloc(sizeof(MazeType));
	if(NULL == temp)
	{
		printf("error!\n");
		return -1;
	}

	memset(temp->array_maze, 0, sizeof(temp->array_maze));
	
	//Matrix transposition, to match the example.
	for(i = 0; i != column; ++i)
	{
		for(j = 0; j != row; ++j)
		{
			temp->array_maze[i][j] = array[j*column + i];
			//temp->array_maze[i][j] = *((int *)array + j*column + i);
			//temp->array_maze[i][j] = array[j][i];
			//temp->array_maze[i][j] = *(*(array+j)+i);
			//printf("%d\n", array[j][i]);
		}
		
	}

	temp->row = column;
	temp->column = row;

	//init the entry point
	temp->entry_point.row = 1;
	temp->entry_point.col = 0;

	//init the exit point
	if(!get_exit_point(temp, &temp->exit_point))
	{
		free(temp);
		temp = NULL;
		return FALSE;
	}
	*maze = temp;
	return TRUE;
}

int init_maze_1(MazeType **maze, int (*array)[ARRAY_COLUMN], int row, int column)
{
	int i, j;
	MazeType *temp = NULL;
	temp = (MazeType *)malloc(sizeof(MazeType));
	if(NULL == temp)
	{
		printf("error!\n");
		return -1;
	}

	memset(temp->array_maze, 0, sizeof(temp->array_maze));
	
	//Matrix transposition, to match the example.
	for(i = 0; i != column; ++i)
	{
		for(j = 0; j != row; ++j)
		{
			//temp->array_maze[i][j] = *((int *)array + j*column + i);
			//temp->array_maze[i][j] = array[j*column + i];
			temp->array_maze[i][j] = array[j][i];
			//temp->array_maze[i][j] = *(*(array+j)+i);
			//printf("%d\n", array[j][i]);
		}
		
	}

	temp->row = column;
	temp->column = row;

	//init the entry point
	temp->entry_point.row = 1;
	temp->entry_point.col = 0;

	//init the exit point
	if(!get_exit_point(temp, &temp->exit_point))
	{
		free(temp);
		temp = NULL;
		return FALSE;
	}
	*maze = temp;
	return TRUE;
}

int init_maze(MazeType **maze, int **array, int row, int column)
{
	int i, j;
	MazeType *temp = NULL;
	temp = (MazeType *)malloc(sizeof(MazeType));
	if(NULL == temp)
	{
		printf("error!\n");
		return -1;
	}

	memset(temp->array_maze, 0, sizeof(temp->array_maze));
	
	//Matrix transposition, to match the example.
	for(i = 0; i != column; ++i)
	{
		for(j = 0; j != row; ++j)
		{
			//temp->array_maze[i][j] = *((int *)array + j*column + i);
			//temp->array_maze[i][j] = array[j*column + i];
			temp->array_maze[i][j] = array[j][i];
			//temp->array_maze[i][j] = *(*(array+j)+i);
			//printf("%d\n", array[j][i]);
		}
		
	}

	temp->row = column;
	temp->column = row;

	//init the entry point
	temp->entry_point.row = 1;
	temp->entry_point.col = 0;

	//init the exit point
	if(!get_exit_point(temp, &temp->exit_point))
	{
		free(temp);
		temp = NULL;
		return FALSE;
	}
	*maze = temp;
	return TRUE;
}

int delete_maze(MazeType *maze)
{
	//This function will cause memory leak: freed maze, but do not free array_maze.
	free(maze);
	return TRUE;
}

void print_maze(MazeType *maze)
{
	int i, j;

	printf("\nDisplay maze:\n");
	for(i = 0; i != maze->row; ++i)
	{
		for(j = 0; j != maze->column; ++j)
		{
			printf("%d ", maze->array_maze[i][j]);
		}
		printf("\n");
	}
	
	return;
}

/*This is the main function to find the path.
    Main idea: 
         Use a stack to store the points which could be passed. Use a loop to get the nearby 
         points, judge if they could pass, if yes, put them in the stack. If a point could not pass
         mark it. When found the exit point, finish.
*/
int maze_path(MazeType *maze, PointType *entry_point, PointType *exit_point)
{
	LinkedNode *stack;
	PointType cur_point;
	ElemType *elem;
	ElemType *temp_elem;
	int rtn = FALSE;

	//set current point as the start point
	cur_point.row = entry_point->row;
	cur_point.col = entry_point->col;

	//init the stack
	create(&stack);


	do
	{
		//if the point could pass, mark it and put it into the stack.
		if(pass(maze, &cur_point))
		{
			mark_passed_point(maze, &cur_point);
			temp_elem = (ElemType *)malloc(sizeof(ElemType));
			if(NULL == temp_elem)
			{
				printf("error!\n");
				destory(stack);
				return -1;
			}
			temp_elem->point.row = cur_point.row;
			temp_elem->point.col = cur_point.col;
			temp_elem->direction = east;

			push(&stack, temp_elem);

			//if it reaches the exit point, print the path
			if(reach_exit(&cur_point, exit_point))
			{
				reverse_stack(&stack);
				printf("Solution: ");
				print_stack(stack);
				printf("\nExit at (%d,%d)\n", maze->exit_point.row, maze->exit_point.col);
				destory(stack);
				return TRUE;
			}
			
			 //search start from the east direction
			rtn = get_next_position(&cur_point, east);       
		}
		else
		{
			//if the current point could not pass, we should pop out the 
			//element from the stack, and take a chance on other nearby points.
			pop(&stack, &elem);

			//other directions are used out, this point is a dead end point.
			while(elem->direction == north && (!is_stack_empty(stack)))
			{
				mark_unavailable_point(maze, &elem->point);
				pop(&stack, &elem);
			}

			//other directions are not used out, have a try!
			if(elem->direction < north)
			{
				elem->direction++;
				temp_elem = (ElemType *)malloc(sizeof(ElemType));
				if(NULL == temp_elem)
				{
					printf("error!\n");
					destory(stack);
					return -1;
				}
				temp_elem->point.row = elem->point.row;
				temp_elem->point.col = elem->point.col;
				temp_elem->direction = elem->direction;

				push(&stack, temp_elem);
				cur_point.row = elem->point.row;
				cur_point.col = elem->point.col;
				rtn = get_next_position(&cur_point, elem->direction);

				//crossed the west or north edge(array index become minus)
				//this condition is only used to avoid this situation.
				if(FALSE == rtn)
				{
					if(elem->direction == west)
					{
						pop(&stack, &elem);
						elem->direction++;

						temp_elem = (ElemType *)malloc(sizeof(ElemType));
						if(NULL == temp_elem)
						{
							printf("error!\n");
							destory(stack);
							return -1;
						}
						temp_elem->point.row = elem->point.row;
						temp_elem->point.col = elem->point.col;
						temp_elem->direction = elem->direction;

						push(&stack, elem);
						rtn = get_next_position(&cur_point, elem->direction);

						//changed to the north direction, but  crossed the north edge.
						if(FALSE == rtn)
						{
							pop(&stack, &elem);
							mark_unavailable_point(maze, &elem->point);
							if(!is_stack_empty(stack))
							{
								pop(&stack, &elem);
								cur_point.row = elem->point.row;
								cur_point.col = elem->point.col;
							}
						}
					}
					else if(elem->direction == north)
					{
						pop(&stack, &elem);
						mark_unavailable_point(maze, &elem->point);
						if(!is_stack_empty(stack))
						{
							pop(&stack, &elem);
							cur_point.row = elem->point.row;
							cur_point.col = elem->point.col;
						}
					}
					else
					{
						//will never come here.
						;
					}
				}


			}
			
		}
		
	}while(!is_stack_empty(stack));

	destory(stack);

	return FALSE;
	
}

int main(void)
{
	int i = 0;
	int j = 0;
	int row = 0;
	int col = 0;
	int **a = NULL;
	int rtn = 0;
	MazeType *maze = NULL;
	int array[ARRAY_ROW][ARRAY_COLUMN] =    \
		{                                
			0,1,0,0,0,0,0,0,0,0,0,
			0,1,1,1,1,1,1,0,0,0,0,
			0,0,0,1,0,0,1,1,0,0,0,
			0,0,1,1,0,0,1,0,0,0,0,
			0,0,0,0,0,1,1,1,1,0,0,
			0,0,1,1,1,1,0,0,1,0,0,
			0,0,0,1,0,0,0,0,0,0,0
		};

	//Method NO.1-------------------Print the fix maze path
	init_maze_3(&maze, (int **)array, ARRAY_ROW, ARRAY_COLUMN);
	rtn = maze_path(maze, &maze->entry_point, &maze->exit_point);
	if(TRUE != rtn)
	{
		printf("Error occured!\n");
	}
	delete_maze(maze);


	//Method NO.2-------------------print custom maze and the path
	//user makes the below maze
	//printf("\n\nOr you can input your own maze: (with 77 numbers either 0 or 1, seperate by space:)\n");
	//for(i = 0; i != ARRAY_ROW; ++i)
	//{
	//	for(j = 0; j != ARRAY_COLUMN; ++j)
	//	{
	//		scanf("%d", &array[i][j]);
	//	}
	//	
	//}
	//init_maze(&maze, array, ARRAY_ROW, ARRAY_COLUMN);
	//print_maze(maze);
	//rtn = maze_path(maze, &maze->entry_point, &maze->exit_point);
	//if(TRUE != rtn)
	//{
	//	printf("Error occured!\n");
	//}
	//delete_maze(maze);


	//Method NO.3-------------------dynamic array
	printf("Enter the row:\n");
	scanf("%d", &row);
	printf("Enter the column:\n");
	scanf("%d", &col);
	a = (int **)malloc(sizeof(int *) * row);
	//a[0] = (int *)malloc(sizeof(int) * row * col);
	for(i = 0; i != row; ++i)
	{
		a[i] = (int *)malloc(sizeof(int) * col);
	}

	//for (i = 0; i != row; ++i)
	//{
	//	a[i] = a[0] + i*col;
	//	//a[i] = a[i-1] + col;
	//}

	printf("\n\nNow input your own maze: (with %d numbers either 0 or 1, separate by space:)\n", row*col);
	for(i = 0; i != row; ++i)
	{
		for(j = 0; j != col; ++j)
		{
			//scanf("%d", (int *)a + j*col + i);
			scanf("%d", &a[i][j]);
			//scanf("%d", *(a+i)+j);
			//scanf("%d", &a[i*row+j]);
		}
		
	}

	init_maze(&maze, a, row, col);
	print_maze(maze);
	rtn = maze_path(maze, &maze->entry_point, &maze->exit_point);
	if(TRUE != rtn)
	{
		printf("Error occured!\n");
	}
	delete_maze(maze);
	
	
	return 0;
}
